МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “ Львівська політехніка ”
Кафедра САП
/
Звіт
до лабораторної роботи № 12
Побудова мінімального кістякового дерева
з курсу «Теорія алгоритмів»
Мета роботи
Мета роботи – отримати навики використання алгоритмів побудови мінімального кістякового дерева в графах.
Теоретичні відомості
2.1. Мінімальне кістякове дерево (або мінімальне покриваюче дерево)
у зв’язаному, зваженому неорієнтованому графі – це кістякове дерево цього графу, яке має мінімально можливу вагу, де під вагою дерева розуміється сума ваг його вхідних ребер.
В загальному випадку, задачу можна сформулювати так: маємо зв’язний, неорієнтований граф з вагами на ребрах G(V, E), у якому V – множина вершин (контактів), а E – множина усіх можливих попарних з’єднань (ребер). Нехай для кожного ребра (U, V) однозначно визначено деяке дійсне число W(u, v) – його вага (довжина або вартість з’єднання). W – називається ваговою функцією. Задача полягає у знаходженні такого зв’язного ациклічного графу T є G , яке містить усі вершини, у яких сумарна вага ребер буде мінімальною.
Властивості мінімальних кістякових дерев:
Максимальне кістякова дерево можна знайти, використовуючи алгоритм Прима (наприклад, замінивши ваги усіх ребер на протилежні: алгоритм не потребує, щоб ваги ребер були тільки додатними величинами).
Мінімальне кістякове дерево є єдиним, якщо вага усіх ребер є різною. Інакше може існувати декілька мінімальних кістякових дерев (вибір одного з них за алгоритмом Прима, залежить від порядку перегляду ребер (вершин) з однаковими вагами).
Мінімальне кістякове дерево є кістяковим деревом з мінімальною вагою найважчого ребра. Цю властивість використовують при застосуванні алгоритму Крускала.
Критерій мінімального кістякового дерева: кістяк є мінімальним тоді і тільки тоді, коли для будь-якого ребра, яке не належить кістяку, цикл, утворений цим ребром, яке додається до кістяку, не містить ребер, важчого за це ребро.
Загальновідомими є наступні алгоритми для знаходження мінімального кістякового дерева:
алгоритм Прима;
алгоритм Крускала;
алгоритм Борувки.
2.2. Алгоритм Прима
Алгоритм Прима — алгоритм побудови мінімального кістякового дерева зваженого зв’язного неорієнтованого графу. Алгоритм вперше був відкритий у 1930 році чеським математиком Войцехом Ярником, потім був перевідкритий Робертом Примом у 1957 році, і незалежно від них, Е. Дейкстрою у 1959 році.
Алгоритм Прима володіє властивістю, що ребра в множині А завжди утворюють єдине дерево. Дерево починається з довільної кореневої вершини і росте до того часу, доки не охопить всі вершини V. На кожному кроці, до дерева А додається “легше” ребро, яке з’єднує дерево і окрему вершину з частин графу, які залишилися. Це правило додає тільки найлегші для А ребра; тобто, по завершенню алгоритму, ребра в А утворюють мінімальне кістякове дерево. Дана стратегія є жадібною, оскільки на кожному кроці до дерева додається ребро, яке вносить мінімально можливий вклад в загальну вагу.
2.3. Алгоритм Крускала
Алгоритм Крускала об’єднує вершини графу у декількох зв’язних компонентах, кожна з яких є деревом. На кожному кроці з усіх ребер, які з’єднують з різних компонент зв’язності, вибирається ребро з найменшою вагою. Необхідно перевірити, чи воно є безпечним. Безпечність ребра гарантується теоремою про безпечність ребра. Так як ребро є найлегшим з усіх ребер, виходячи з даної компоненти, воно буде безпечним. У алгоритмі Крускала вибір на кожному кроці безпечного ребра реалізується таким чином: усі ребра графу G перебираються за зростанням ваги. Для чергового ребра перевіряється, чи не лежать кінці ребра в різних компонентах зв’язності, і якщо так, то ребро додається і компоненти об’єднуються.
2.4. Алгоритм Борувки
Нехай дано зв’язний неорієнтований G(V;E) і на ньому задана вагова функція. Нехай А – проміжний кістяковий ліс для графу V. На першому кроці A складається з усіх вершин G і пустої множини ребер. Спочатку, на кожній фазі алгоритму Борувки, для кожної компонен...
